package com.fr.lintcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月6日
*时间：上午10:51:56
*/
public class Q132 {
    /**
     * @param board: A list of lists of character
     * @param words: A list of string
     * @return: A list of string
     */
    Set<String> rs = new HashSet<>();
    TrieNode root = new TrieNode();

    public ArrayList<String> wordSearchII(char[][] board, ArrayList<String> words) {
        ArrayList<String> result = new ArrayList<>();
        if (board == null || board[0] == null || words == null || words.size() <= 0) {
            return result;
        }
        int n = board.length;
        int m = board[0].length;
        for (String s : words) {
            addWord(s);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                List<Point> list = new ArrayList<>();
                Point p = new Point();
                p.x = i;
                p.y = j;
                list.add(p);
                check(board, root, i, j, list, n, m);
            }
        }
        return new ArrayList<>(rs);
    }

    private void check(char[][] board, TrieNode node, int i, int j, List<Point> list, int n, int m) {
        List<Point> l = new ArrayList<>(list);
        char c = board[i][j];
        TrieNode now = node.child.get(c);
        if (now == null) {
            return;
        }
        if (now.isEnd) {
            save(board, list);
        }
        if (i - 1 >= 0) {
            if (!checkPoint(i - 1, j, l)) {
                Point p = new Point();
                p.x = i - 1;
                p.y = j;
                l.add(p);
                check(board, now, i - 1, j, l, n, m);
                l.remove(p);
            }
        }
        if (j - 1 >= 0) {
            if (!checkPoint(i, j - 1, l)) {
                Point p = new Point();
                p.x = i;
                p.y = j - 1;
                l.add(p);
                check(board, now, i, j - 1, l, n, m);
                l.remove(p);
            }
        }
        if (i + 1 < n) {
            if (!checkPoint(i + 1, j, l)) {
                Point p = new Point();
                p.x = i + 1;
                p.y = j;
                l.add(p);
                check(board, now, i + 1, j, l, n, m);
                l.remove(p);
            }
        }
        if (j + 1 < m) {
            if (!checkPoint(i, j + 1, l)) {
                Point p = new Point();
                p.x = i;
                p.y = j + 1;
                l.add(p);
                check(board, now, i, j + 1, l, n, m);
                l.remove(p);
            }
        }
    }

    private boolean checkPoint(int i, int j, List<Point> l) {
        for (Point p : l) {
            if (p.x == i && p.y == j) {
                return true;
            }
        }
        return false;
    }

    private void save(char[][] board, List<Point> list) {
        String s = "";
        for (Point p : list) {
            s += board[p.x][p.y];
        }
        rs.add(s);
    }

    private void addWord(String s) {
        TrieNode current = root;
        for (char c : s.toCharArray()) {
            TrieNode tmp = current.child.get(c);
            if (tmp == null) {
                tmp = new TrieNode();
                tmp.c = c;
                current.child.put(c, tmp);
            }
            current = tmp;
        }
        current.isEnd = true;
    }

    class Point {
        int x;
        int y;
    }

    class TrieNode {
        char c;
        boolean isEnd = false;
        Map<Character, TrieNode> child = new HashMap<>();
    }

    @Test
    public void testA() {
        /**
         * doaf
         * agai
         * dcan
         * "dog", "dad", "dgdg", "can", "again"
         * */
        char[][] board = { { 'd', 'o', 'a', 'f' }, { 'a', 'g', 'a', 'i' }, { 'd', 'c', 'a', 'n' } };
        ArrayList<String> words = new ArrayList<>();
        words.add("dog");
        words.add("dad");
        words.add("dgdg");
        words.add("can");
        words.add("again");
        System.out.println(wordSearchII(board, words));
    }

}
